Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10- The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
Average Rating: 4.88 (102 votes)
Solution
It is advisable to approach Maximum Subarray problem first before approaching this problem. The intuition acquired from that problem will help a lot with this problem.
Approach 1: Brute Force
Intuition
The most naive way to tackle this problem is to go through each element in nums, and for each element, consider the product of every a contiguous subarray starting from that element. This will result in a cubic runtime.
for i in [0...nums-1]:
for j in [i..nums-1]:
accumulator = 1
for k in [i..j]:
accumulator = accumulator * nums[k]
result = max(result, accumulator)
We can improve the runtime from cubic to quadratic by removing the innermost for loop in the above pseudo code. Rather than calculating the product of every contiguous subarray over and over again, for each element in nums (the outermost for loop), we accumulate the products of contiguous subarrays starting from that element to subsequent elements as we go through them (the second for loop). By doing so, we only need to multiply the current number with accumulated product to get the product of numbers up to the current number.
Implementation
Complexity Analysis
-
Time complexity : O(N2) where N is the size of
nums. Since we are checking every possible contiguous subarray following every element innumswe have quadratic runtime. -
Space complexity : O(1) since we are not consuming additional space other than two variables:
resultto hold the final result andaccuto accumulate product of preceding contiguous subarrays.
Approach 2: Dynamic Programming
Intuition
Rather than looking for every possible subarray to get the largest product, we can scan the array and solve smaller subproblems.
Let's see this problem as a problem of getting the highest combo chain. The way combo chains work is that they build on top of the previous combo chains that you have acquired. The simplest case is when the numbers in nums are all positive numbers. In that case, you would only need to keep on multiplying the accumulated result to get a bigger and bigger combo chain as you progress.
However, two things can disrupt your combo chain:
- Zeros
- Negative numbers
Zeros will reset your combo chain. A high score which you have achieved will be recorded in placeholder result. You will have to restart your combo chain after zero. If you encounter another combo chain which is higher than the recorded high score in result, you just need to update the result.
Negative numbers are a little bit tricky. A single negative number can flip the largest combo chain to a very small number. This may sound like your combo chain has been completely disrupted but if you encounter another negative number, your combo chain can be saved. Unlike zero, you still have a hope of saving your combo chain as long as you have another negative number in nums (Think of this second negative number as an antidote for the poison that you just consumed). However, if you encounter a zero while you are looking your another negative number to save your combo chain, you lose the hope of saving that combo chain.
While going through numbers in nums, we will have to keep track of the maximum product up to that number (we will call max_so_far) and minimum product up to that number (we will call min_so_far). The reason behind keeping track of max_so_far is to keep track of the accumulated product of positive numbers. The reason behind keeping track of min_so_far is to properly handle negative numbers.
max_so_far is updated by taking the maximum value among:
- Current number.
- This value will be picked if the accumulated product has been really bad (even compared to the current number). This can happen when the current number has a preceding zero (e.g.
[0,4]) or is preceded by a single negative number (e.g.[-3,5]).
- This value will be picked if the accumulated product has been really bad (even compared to the current number). This can happen when the current number has a preceding zero (e.g.
- Product of last
max_so_farand current number.- This value will be picked if the accumulated product has been steadily increasing (all positive numbers).
- Product of last
min_so_farand current number.- This value will be picked if the current number is a negative number and the combo chain has been disrupted by a single negative number before (In a sense, this value is like an antidote to an already poisoned combo chain).
min_so_far is updated in using the same three numbers except that we are taking minimum among the above three numbers.
In the animation below, you will observe a negative number -5 disrupting a combo chain but that combo chain is later saved by another negative number -4. The only reason this can be saved is because of min_so_far. You will also observe a zero disrupting a combo chain.
Implementation
Complexity Analysis
-
Time complexity : O(N) where N is the size of
nums. The algorithm achieves linear runtime since we are going throughnumsonly once. -
Space complexity : O(1) since no additional space is consumed rather than variables which keep track of the maximum product so far, the minimum product so far, current variable, temp variable, and placeholder variable for the result.
September 10, 2020 3:08 AM
Am I the only one who thinks these solution however elegant are hard to come up in realtime ?
July 16, 2020 1:23 PM
Approach 2 Explanation is Pure GOLD!!
August 17, 2020 6:07 AM
How do I come up with such approaches naturally? is it just practice? cause this is amazing
O(n) simple solution using two passes of the array. One in forward direction. One in backward direction.
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE;
int product=1;
for(int num : nums){
product *= num;
max = Math.max(product,max);
if(product == 0)product = 1;
}
product = 1;
for(int i=nums.length-1;i>=0;i--){
product *= nums[i];
max = Math.max(product,max);
if(product ==0) product = 1;
}
return max;
}
}
September 25, 2020 5:14 PM
Please change this to hard.
July 17, 2020 2:05 PM
elegant, it seems natural extension of Kadane's algorithm.
The explanation of the solution is really smart and clear, but I am more interested in the thinking process that led to such an elegant solution. I still can't see what is the optimal substructure construct for this dynamic programming problem, and how would a top-down approach look like (I think the solution presented is a bottom up approach). Can anyone help me with a run-through of the top down solution and the optimal substructure?
Follow up question I've received is to find the beginning and ending indexes of the largest subarray
For me, for O(N), it was hard to implement without too many ifs
August 30, 2020 11:29 AM
why do you call it a dynamic programming?
xxxxxxxxxxclass Solution {public: int maxProduct(vector<int>& nums) { int ans = nums[0]; int maxc = nums[0], minc = nums[0]; for(int i=1;i<nums.size();i++) { if(nums[i] < 0) swap(maxc, minc); maxc = max(nums[i], maxc*nums[i]); minc = min(nums[i], minc*nums[i]); ans = max(ans, maxc); } return ans; }};